package leetcode.D500.T496;

import java.util.*;

class Solution {
    /* 一刷
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> dq = new LinkedList<>();
        for(int i=nums2.length-1; i>=0; --i) {
            while(!dq.isEmpty() && dq.getLast() < nums2[i]) {
                dq.removeLast();
            }
            int t = dq.isEmpty() ? -1 : dq.getLast();
            map.put(nums2[i], t);
            dq.addLast(nums2[i]);
        }
        int[] result = new int[nums1.length];
        for(int i=0; i<result.length; ++i) {
            result[i] = map.get(nums1[i]);
        }
        return result;
    }*/
    // 二刷
    /*public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Deque<Integer> dq = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=nums2.length-1; i >= 0; --i) {
            while(!dq.isEmpty() && dq.getLast() <=nums2[i]) {
                dq.removeLast();
            }
            int temp = dq.isEmpty() ? -1 : dq.getLast();
            dq.addLast(nums2[i]);
            map.put(nums2[i], temp);
        }
        for(int i=0; i<result.length; ++i) {
            result[i] = map.get(nums1[i]);
        }
        return result;
    }*/

    // 三刷
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Deque<Integer> dq = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], 0);
        }
        for(int i=nums2.length-1; i>=0; --i) {
            if (!map.containsKey(nums2[i])) {
                dq.addLast(nums2[i]);
                continue;
            }
            while (!dq.isEmpty() && dq.getLast() <= nums2[i]) {
                dq.removeLast();
            }
            map.put(nums2[i], dq.isEmpty() ? -1 : dq.getLast());
            dq.addLast(nums2[i]);
        }
        for(int i=0; i<result.length; ++i) {
            result[i] = map.get(nums1[i]);
        }
        return result;
    }
}
